#include<iostream>

struct ListNode
{   
    int val;
    ListNode *next;
    ListNode():val(0),next(nullptr){}
    ListNode(int x):val(val),next(nullptr){}
    ListNode(int x, ListNode* ptr):val(x),next(ptr){}
};

ListNode *detectCycle(ListNode *head) {
    ListNode* fast = head;
    ListNode* slow = head;

    while(fast!=nullptr && fast->next!=nullptr)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            fast = head;
            while(fast != slow)
            {
                slow=slow->next;
                fast=fast->next;
            }
            return fast;
        }
    }
    return nullptr;
}

void TestCase1()
{
    //case 1
    ListNode *case1_node0 = new ListNode(3);
    ListNode *case1_node1 = new ListNode(2);
    ListNode *case1_node2 = new ListNode(0);
    ListNode *case1_node3 = new ListNode(-4);
    case1_node0->next = case1_node1;
    case1_node1->next = case1_node2;
    case1_node2->next = case1_node3;
    case1_node3->next = case1_node1;

    ListNode *head = detectCycle(case1_node0);
    // output
}

void TestCase2()
{
    //case 2
    ListNode *case2_node0 = new ListNode(1);
    ListNode *case2_node1 = new ListNode(2);
    case2_node0->next = case2_node1;
    case2_node1->next = case2_node0;

    ListNode *head = detectCycle(case2_node0);
    // output
}

void TestCase3()
{
    //case 3
    ListNode *case3_node0 = new ListNode(1);

    ListNode *head = detectCycle(case3_node0);
    // output
}

int main()
{
    TestCase1();
    TestCase2();
    TestCase3();
    return 0;
}